package LC;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * @ClassName LC18
 * @Description: TODO
 * @Author hl
 * @Date 2021/3/29
 * @Version V1.0
 **/
public class LC18 {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-3;i++){
            if(i-1>=0&&nums[i]==nums[i-1]) continue;//去重

            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
            if(nums[i]+nums[nums.length-3]+nums[nums.length-2]+nums[nums.length-1]<target) continue;
            int sTarget=target-nums[i];
            for(int j=i+1;j<nums.length-2;j++){
                if(j-1>=i+1&&nums[j]==nums[j-1]) continue;//去重

                if(nums[j]+nums[j+1]+nums[j+2]>sTarget) break;
                if(nums[j]+nums[nums.length-2]+nums[nums.length-1]<sTarget) continue;
                int start=j+1,end=nums.length-1;
                while(start<end){

                    if(nums[j]+nums[start]+nums[end]==sTarget){
                        res.add(Arrays.asList(nums[i],nums[j],nums[start],nums[end]));
                        while(start+1<end&&nums[start]==nums[start+1]) start++;
                        while(end-1>start&&nums[end]==nums[end-1]) end--;
                        start++;
                    }else{
                       if(nums[j]+nums[start]+nums[end]>sTarget) end--;
                       else start++;
                    }
                }

            }
        }
        return res;
    }

    public static void main(String[] args) {
        int []nums={0,4,-5,2,-2,4,2,-1,4};

        List<List<Integer>> list=fourSum(nums,12);
        System.out.println(list.toString());
    }


}
